/**
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
 *
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 *
 *https://leetcode.cn/problems/subsets-ii/
 */
class SubsetsWithDup {
    List<List<Integer>> ret=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums,0,nums.length,new LinkedList<Integer>());
        return ret;
    }
    public void dfs(int[] nums,int begin,int len,Deque<Integer> qu){
        ret.add(new LinkedList<>(qu));
        for(int i=begin;i<len;i++){
            if(i>begin&&nums[i-1]==nums[i]){
                continue;
            }
            qu.offerLast(nums[i]);
            dfs(nums,i+1,len,qu);
            qu.pollLast();
        }
    }
}